package com.kuang.matrix;

/*
 *   给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 * */


/**
 * @author kjx
 */
public class SetZeroes {

    //最简单的方法肯定是复制数组，这种复制的方法永远是数组类的题目最直观最通用的方法
    //但是这个题这样做就没有意义了，第一种方法用标记数组，空间复杂度为 m + n，比复制数组的 m*n 好一点
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] rowFlag = new boolean[m];
        boolean[] colFlag = new boolean[n];
        //第一次遍历填充标记数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rowFlag[i] = colFlag[j] = true;
                }
            }
        }
        //第二次遍历根据标记数组进行矩阵置零
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rowFlag[i] || colFlag[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
    //事先说明，第一种方法综合可读性是最优秀的算法，但是捏，评价一个算法的性能一般是不看可读性的
    //毕竟算法并不服务于生产环境


    //第二种方法，空间复杂度为O(1)
    //这种算法的思路很简单，第一种方法我们用了一行一列两个标记数组，那么我们其实是可以把这两个标记数组放到原数组的第一行第一列的
    //但是如果用原数组的第一行第一列,那么原数组就会发生改变,因此我们还需要额外的变量来标识第一行第一列，用于复原原数组
    //这种方法纯纯麻烦，为了节省那点空间导致可读性变差很多
    public void setZeroes2(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        //先统计第一行第一列是否有0,
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                flagRow0 = true;
                break;
            }
        }
        //然后把第一行第一列当成方法一中的标记数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        //根据标记变量，如果第一行第一列<<曾经>>有0，再去置0
        if (flagCol0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
    //这种思路在很多数组题都有影子，就是把原数组当成标记数组，但是需要额外记录用于复原
}
